{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4、栈与队列\n",
    "\n",
    "![stack.png](img/c4_stack_queue/stack.png)\n",
    "\n",
    "## 栈与递归\n",
    "\n",
    "函数调用和递归调用都通过栈完成。调用栈中的各帧，依次对应一个尚未返回的调用实例（即当前的活跃函数实例 active function instance)，即每次调用时，都相应创建帧，记录调用实例在二进制程序中的返回地址，局部变量、传入参数等信息，并将该帧压入调用栈。\n",
    "\n",
    "\n",
    "# 栈的应用\n",
    "\n",
    "## 逆序输出\n",
    "\n",
    "### 进制转换\n",
    "\n",
    "从 10 进制转为 $\\lambda$ 进制，如 $12345_{(10)} = 30071_{(8)}$\n",
    "\n",
    "```cpp\n",
    "//栈的应用\n",
    "// 逆序输出 1. 进制转换\n",
    "void convert(Stack<char>& s, int n, int base) { //十进制数 n 到 base 进制的转换\n",
    "    static char digit[] //0<n, 1<base<=16, 新进制下的数位符号，可视base取值适当扩充\n",
    "        = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };\n",
    "\n",
    "    while (n>0) { //由低到高，逐一计算出新进制下的各数位\n",
    "        int remainder = (int) n % base; //余数即为当前位\n",
    "        s.push(digit[remainder]);\n",
    "        n /= base;\n",
    "    }\n",
    "}//新进制下由高到低的各数位，自顶而下保存于栈中\n",
    "\n",
    "void convert_number(int n, int base) {\n",
    "    Stack<char> s = Stack<char>();\n",
    "\n",
    "    convert(s, 12345, 8);\n",
    "    cout << \"12345(10) --> \";\n",
    "    while( !s.empty() ){\n",
    "        cout << s.pop();\n",
    "    }\n",
    "    cout << \"(8)\" << endl;\n",
    "}\n",
    "\n",
    "convert_number(12345, 8); //30071\n",
    "```\n",
    "\n",
    "### 栈混洗\n",
    "\n",
    "考查三个栈 A, B 和 S。其中 B 和 S 为空，A 含有 n 个元素，自顶向下构成输入序列 `A = <a1, a2, ..., an]`。\n",
    "\n",
    "只允许 2 种操作：\n",
    "\n",
    "+ 将 A 中的元素 pop 出随即 push 到 S\n",
    "+ 将 S 中的元素 pop 出随即 push 到 B\n",
    "\n",
    "则经 n 次这样的操作后，A 中的元素全部 B 中，而 B 中的元素序列即为原输入序列的一个栈混洗 stack permutation。\n",
    "\n",
    "下面是一个栈混洗实例，上左为 A（输入），上右为 B（输出），下面为 S（临时栈）：\n",
    "\n",
    "![stack_permutation_instance.png](img/c4_stack_queue/stack_permutation_instance.png)\n",
    "\n",
    "可看出，对于长度为 n 的输入序列，每一个栈混洗对应于由 n 次 push 和 n 次 pop 构成的某一个合法操序列，比如上面的 `[3, 2, 4, 1]` 即对应于 `{push, push, push, pop, pop, push, pop, pop }`。反之，由 n 次 push 和 n 次 pop 构成的任何操作序列，只要满足 **任一前缀中的 push 不少于 pop** 这一限制，则该序列也必然对应于某个栈混洗。\n",
    "\n",
    "#### 栈混洗数目\n",
    "\n",
    "设长度为 n 的输入序列，共有 SP(n) 个栈混洗，则 SP(1) = 1， 考查元素从 S 中 pop 出随即 push 入 B 时，此时设 B 中已经有 k-1 个元素，那么 A 中还有 n-k 个元素，此时的 栈混洗数为 $SP(k-1) \\cdot SP(n-k)$, 根据 k 的可能取值，则 \n",
    "\n",
    "$$SP(n) = \\sum_{k=1}^n SP(k-1) \\cdot SP(n-k)$$\n",
    "\n",
    "值恰好是著名的 catalan 数，为 $catalan(n) = (2n)!/（(n+1)! \\cdot n!)$\n",
    "\n",
    "![stack_permutation_count.png](img/c4_stack_queue/stack_permutation_count.png)\n",
    "\n",
    "#### 甄别是否合法栈混洗\n",
    "\n",
    "当 n=3 时， `<1,2,3]` 共有 `6!/(4!*3!) = 5` 种合法栈混洗，而其全排序为 3!=6 种，只有 `B = [3, 1, 2>` 是非法的。\n",
    "\n",
    "对于输入序列中有 `1<=i<j<k<=n` 时，如果输出中有 `[..., k,... i, ....,j,...>`，即必非栈混洗。\n",
    "\n",
    "进一步地，对于 `i<j`，输出中必不含 模式 `[..., j+1, ..., i,..., j...>`。\n",
    "\n",
    "充要性： A permutation is a stack permutation, it does **NOT** involve the permutation 312。(Kunth, 1968)\n",
    "\n",
    "![stack_permutation_check.png](img/c4_stack_queue/stack_permutation_check.png)\n",
    "\n",
    "\n",
    "### 括号匹配\n",
    "\n",
    "合法的栈混洗中，满足 **任一前缀中的 push 不少于 pop** 这一限制。因此一个合法的栈混洗，刚好对应于一种括号匹配。如上面的 `{push, push, push, pop, pop, push, pop, pop }` 对应 `((())())`。\n",
    "\n",
    "```cpp\n",
    "//栈的应用 2. 括号匹配\n",
    "bool parentheses_match(const char exp[], int lo, int hi) { //表达式括号匹配检查，可兼顾三种括号\n",
    "    Stack<char> s = Stack<char>(); //使用栈记录已发现但尚未匹配的括号\n",
    "    for( int i=lo; i<hi; i++) {\n",
    "        switch( exp[i] ){\n",
    "            case '(': case '[': case '{':  //左括号直接进栈\n",
    "                s.push(exp[i]); \n",
    "                break;\n",
    "            case ')':  //右括号若与栈顶失配，则表达式必不匹配\n",
    "                if (s.empty() || s.pop() != '(') {\n",
    "                    return false;\n",
    "                }\n",
    "                break;\n",
    "            case ']':\n",
    "                if (s.empty() || s.pop() != '[') {\n",
    "                    return false;\n",
    "                }\n",
    "                break;\n",
    "            case '}':\n",
    "                if (s.empty() || s.pop() != '{') {\n",
    "                    return false;\n",
    "                }\n",
    "                break;\n",
    "        default: //非括号字符一律忽略\n",
    "                break;\n",
    "        }\n",
    "    }\n",
    "    return s.empty();\n",
    "}\n",
    "\n",
    "\n",
    "\n",
    "char* parentheses_str1 = \"a / ( b [ i - 1 ] [ j + 1 ] + c [ i + 1 ] [ j - 1 ] ) * 2\";\n",
    "char* parentheses_str2 = \"a / ( b [ i - 1 ] [ j + 1 ] ) + c [ i + 1 ] [ j - 1 ] ) * 2\";\n",
    "cout << parentheses_str1 << \" is match: \" << parentheses_match(parentheses_str1, 0, 56) << endl;\n",
    "cout << parentheses_str2 << \" is match: \" << parentheses_match(parentheses_str2, 0, 58) << endl;\n",
    "```\n",
    "\n",
    "### 延迟缓冲\n",
    "\n",
    "如中缀表达式求值时，必须等所有表达式字符全部扫描后，才能进行求值，此时用栈来缓存。\n",
    "\n",
    "下面的代码中，利用了栈来求值中缀表达式的值，并将中缀表达式转换成了后缀表达式（逆波兰表达式）。\n",
    "\n",
    "```cpp\n",
    "//习题 4-6\n",
    "// 输出一个浮点数并压入栈中\n",
    "float readNumber(char* &S, Stack<float> & opnd) {\n",
    "    opnd.push(0); //初始化为 0\n",
    "    char c = *S;\n",
    "    bool is_decimal = false; //是否处理的是小数部分\n",
    "    float decimal_base = 0.1;\n",
    "    while ( *S ) {\n",
    "        if (isdigit(*S)){\n",
    "            float val = opnd.pop();\n",
    "            int digit = int(*S)-0x30;\n",
    "\n",
    "            if (!is_decimal) //处理非小数部分， x = x*10 + y\n",
    "                opnd.push( val * 10 + digit );\n",
    "            else { //处理小数部分，x=x+y*decimal_base\n",
    "                opnd.push( val + digit*decimal_base );\n",
    "                decimal_base *= 0.1; // 当有小数时，计算下一个数位的基数\n",
    "            }\n",
    "            S++;\n",
    "        }\n",
    "        else if ( *S == '.' ) {\n",
    "            is_decimal = true;\n",
    "            decimal_base = 0.1;\n",
    "            S++;\n",
    "        }\n",
    "        else break;\n",
    "    }\n",
    "    return opnd.top();\n",
    "}\n",
    "\n",
    "float calcu(char op, float opnd) { //实施一元计算\n",
    "    if (op == '!'){\n",
    "        float ret = 1;\n",
    "        for (int i=(int)opnd; i>1; i--)\n",
    "            ret *= i;\n",
    "        return ret;\n",
    "    }\n",
    "    return -1;\n",
    "}\n",
    "\n",
    "float calcu( float pOpnd1, char op, float pOpnd2 ) {//实施二元计算，结果入栈\n",
    "    switch(op){\n",
    "        case '+':\n",
    "            return pOpnd1 + pOpnd2; break;\n",
    "        case '-':\n",
    "            return pOpnd1 - pOpnd2; break;\n",
    "        case '*':\n",
    "            return pOpnd1 * pOpnd2; break;\n",
    "        case '/':\n",
    "            return pOpnd1 / pOpnd2; break;\n",
    "        case '^':\n",
    "            return pow(pOpnd1, pOpnd2); break;\n",
    "    }\n",
    "    return -1;\n",
    "}\n",
    "\n",
    "void append( string &RPN, char op){ //读入操作数，并将其接至 PRN 末尾\n",
    "    RPN = RPN + op;\n",
    "}\n",
    "\n",
    "void append( string &RPN, float opnd){ //读入操作数，并将其接至 PRN 末尾\n",
    "    ostringstream ss;\n",
    "    ss << opnd;\n",
    "    RPN  = RPN + ss.str();\n",
    "}\n",
    "\n",
    "void append( string &RPN, double opnd){ //读入操作数，并将其接至 PRN 末尾\n",
    "    ostringstream ss;\n",
    "    ss << opnd;\n",
    "    RPN  = RPN + ss.str();\n",
    "}\n",
    "\n",
    "//栈的应用 3. 中缀表达式求值\n",
    "#define N_OPTR 9 //运算符总数\n",
    "typedef enum { ADD, SUB, MUL, DIV, POW, FAC, L_P, R_P, EOE } Operator; //运算符集合\n",
    "//加，减，乘，除，乘方，阶乘，左括号，右括号，起始符与终止符\n",
    "\n",
    "const char pri[N_OPTR][N_OPTR] = { //运算符优先等级[栈顶][当前]\n",
    "    /*          |------------当前运算符-----------| */\n",
    "    /*          +     -     *     /     ^     !     (     )     \\0 */\n",
    "    /* -- + */ '>',  '>',  '<',  '<',  '<',  '<',  '<',  '>',  '>',    \n",
    "    /* |  - */ '>',  '>',  '<',  '<',  '<',  '<',  '<',  '>',  '>',    \n",
    "    /* 栈 * */ '>',  '>',  '>',  '>',  '<',  '<',  '<',  '>',  '>',    \n",
    "    /* 顶 / */ '>',  '>',  '>',  '>',  '<',  '<',  '<',  '>',  '>',    \n",
    "    /* 运 ^ */ '>',  '>',  '>',  '>',  '>',  '<',  '<',  '>',  '>',    \n",
    "    /* 算 ! */ '>',  '>',  '>',  '>',  '>',  '>',  ' ',  '>',  '>',    \n",
    "    /* 符 ( */ '<',  '<',  '<',  '<',  '<',  '<',  '<',  '=',  ' ',    \n",
    "    /* |  ) */ ' ',  ' ',  ' ',  ' ',  ' ',  ' ',  ' ',  ' ',  ' ',    \n",
    "    /* --\\0 */ '<',  '<',  '<',  '<',  '<',  '<',  '<',  ' ',  '='    \n",
    "};\n",
    "\n",
    "int op2index(char op) {\n",
    "    switch(op){\n",
    "        case '+': return 0; break;\n",
    "        case '-': return 1; break;\n",
    "        case '*': return 2; break;\n",
    "        case '/': return 3; break;\n",
    "        case '^': return 4; break;\n",
    "        case '!': return 5; break;\n",
    "        case '(': return 6; break;\n",
    "        case ')': return 7; break;\n",
    "        case '\\0': return 8; break;\n",
    "        default: return -1; break;\n",
    "    }\n",
    "}\n",
    "\n",
    "char orderBetween(char op1, char op2) { //视其与栈顶运算符之间优先级高低分别处理\n",
    "    int index1 = op2index(op1);\n",
    "    int index2 = op2index(op2);\n",
    "    return pri[index1][index2];\n",
    "}\n",
    "\n",
    "float evaluate( char* S, string & RPN) { //对已剔除空白符的表达式求值，并转换为逆波兰式 RPN\n",
    "    Stack<float> opnd; //运算数栈\n",
    "    Stack<char> optr; //运算符栈\n",
    "\n",
    "    optr.push('\\0'); //尾哨兵 '\\0' 也作为头哨兵首先入栈\n",
    "\n",
    "    while (!optr.empty()) { //在运算符栈非空之前，逐个处理表达式中各字符\n",
    "        if ( isdigit(*S) ) { //若当前字符为操作数，则\n",
    "            readNumber(S, opnd);\n",
    "            append( RPN, opnd.top() ); //读入操作数，并将其接至 PRN 末尾\n",
    "        }\n",
    "        else {//若当前字符为运算符\n",
    "            switch( orderBetween(optr.top(), *S) ) { //视其与栈顶运算符之间优先级高低分别处理\n",
    "                case '<': //栈顶运算符低优先级时\n",
    "                    optr.push( *S ); S++; //计算推迟，当前运算符进栈\n",
    "                    break;\n",
    "                case '=': //优先级相等，（当前运算符为右括号或尾部哨兵\\0)时\n",
    "                    optr.pop(); S++; //脱括号并接收下一个字符\n",
    "                    break;\n",
    "                case '>':{ //栈顶运算符高优先级时，可实施相应的计算，并将结果重新入栈\n",
    "                    char op = optr.pop(); append( RPN, op ); //栈顶运算符出栈并续接至 RPN 末尾\n",
    "                    if ( '!' == op ) { //! 为一元操作符\n",
    "                        float pOpnd = opnd.pop();\n",
    "                        opnd.push( calcu( op, pOpnd ) ); //实施一元计算，结果入栈\n",
    "                    } else { //其它都为二元操作符\n",
    "                        float pOpnd2 = opnd.pop(), pOpnd1 = opnd.pop();\n",
    "                        opnd.push( calcu( pOpnd1, op, pOpnd2 ) ); //实施二元计算，结果入栈\n",
    "                    }\n",
    "                    break;\n",
    "                }\n",
    "                default:\n",
    "                    exit(-1); //逢语法错误，不做处理直接退出\n",
    "                    break;\n",
    "            } //switch\n",
    "        }\n",
    "    }//while\n",
    "\n",
    "    return opnd.pop(); //弹出并返回最后的计算结果\n",
    "}\n",
    "\n",
    "\n",
    "char* exp = \"(1+2)*3^4\";\n",
    "string RPN = \"\";\n",
    "cout << exp << \"=\" << evaluate(exp, RPN) << endl; //(1+2)*3^4=243\n",
    "cout << \"RPN is:\" << RPN << endl; //RPN is:12+34^*\n",
    "```\n",
    "\n",
    "### 逆波兰表达式\n",
    "\n",
    "手工将中缀表达式转换成后缀表达式：\n",
    "\n",
    "+ 操作数的位置保持不变\n",
    "+ 运算符的位置，恰好就是其对应的操作数均就绪时的后面。\n",
    "\n",
    "例如： `( 0 ! + 1 ) * 2 ^ ( 3 ! + 4 ) - ( 5 ! - 67 - ( 8 + 9 ) )`，转换成 `0！1+  2  3！4+^*  5！ 67- 89+--`。\n",
    "\n",
    "## 试探回溯法\n",
    "\n",
    "### 八皇后问题\n",
    "\n",
    "国际象棋中皇后的热力范围覆盖其所在的水平线、垂直线及两条对角线，考查在 nXn 的棋盘上放置 n 个皇后，如何使得她们互不攻击。\n",
    "\n",
    "由鸽巢原理知，n 行 n 列棋盘上至多只能放 n 个皇后，反之，n 个皇后在 nXn 棋盘上的可行棋局通常也存在。\n",
    "\n",
    "![8queens.png](img/c4_stack_queue/8queens.png)\n",
    "\n",
    "#### 算法实现：\n",
    "\n",
    "基于试探回溯策略。既然每行能且仅能放置一个皇后，故首先将各皇后分配至每一行。然后从空棋盘开始，逐个尝试着将她们放置到无冲突的某列。每设置好一个皇后，再继续试探下一个。若当前皇后在任何列都会造成冲突，则后续皇后的试探都将是徒劳的，故此时应该回溯到上一个皇后进行再试探。\n",
    "\n",
    "迭代版本中用一个栈来保存皇后的位置，开始为空棋盘，并从原点位置出发开始尝试。当栈中的元素个数等于棋盘行（列）数时，则得到一个解。\n",
    "\n",
    "```cpp\n",
    "//国际象棋中皇后的热力范围覆盖其所在的水平线、垂直线及两条对角线，考查在 nXn 的棋盘上放置 n 个皇后，如何使得她们互不攻击。\n",
    "//由鸽巢原理知，n 行 n 列棋盘上至多只能放 n 个皇后，反之，n 个皇后在 nXn 棋盘上的可行棋局通常也存在。\n",
    "struct Queen { //皇后类\n",
    "    int x, y; //皇后在棋盘上的位置坐标\n",
    "    Queen(int xx=0, int yy=0): x(xx), y(yy) {};\n",
    "    bool operator == (Queen const& q) const { //重载判等操作符，以检测不同皇后之间可能的冲突\n",
    "        return (x == q.x) // 行冲突，这一情况其实并不会发生，可省略\n",
    "            || (y == q.y)\n",
    "            || (x+y == q.x+q.y) //右上、左下对角线冲突\n",
    "            || (x-y == q.x-q.y); // 左上、右下对象线冲突\n",
    "    }\n",
    "\n",
    "    bool operator != (Queen const& q) const { return ! (*this == q); }\n",
    "\n",
    "};\n",
    "\n",
    "int nSolu = 0; // 保存 N 皇后问题的解的个数\n",
    "int nCheck = 0; //保存 N 皇后问题求解过程中的尝试次数\n",
    "\n",
    "//迭代版本中用栈保存位置。\n",
    "//开始为空棋盘，并从原点位置出发开始尝试\n",
    "void placeQueens( int N ){ //N 皇后算法迭代版：采用试探/回溯策略，借助栈记录查找的结果\n",
    "    Stack<Queen> solu; //存放（部分）解的栈\n",
    "    Queen q(0, 0); //从原点位置出发\n",
    "\n",
    "    do { //反复试探与回溯\n",
    "        if ( N <= solu.size() || N <= q.y ) { //若已出界，则\n",
    "            q = solu.pop(); //回溯一行，并接着试探该行中的下一列\n",
    "            q.y++; \n",
    "        } \n",
    "        else { //否则，试探下一行\n",
    "            while ( (q.y < N) && ( 0 <= solu.find(q)) ) { //通过与已有皇后的对比\n",
    "                q.y++; //尝试找到可摆放下一皇后的列\n",
    "                nCheck++;\n",
    "            }\n",
    "\n",
    "            if (q.y < N) { //若找到可摆放的列，则\n",
    "                solu.push(q); //摆上当前皇后，并\n",
    "                if (N <= solu.size() ) {  //若部分解已成为全局解，则通过全局变量 nSolu 计数\n",
    "                    nSolu++;\n",
    "                }\n",
    "\n",
    "                q.x++; //转入下一行，从第 0 列开始，试探下一皇后\n",
    "                q.y = 0;\n",
    "            }\n",
    "        }\n",
    "    } while( ( 0<q.x ) || (q.y < N) );\n",
    "}\n",
    "\n",
    "\n",
    "placeQueens(8);\n",
    "cout << \"8 Queens solutions = \" << nSolu << endl; //92\n",
    "cout << \"8 Queens solution checks = \" << nCheck << endl; //13664\n",
    "```\n",
    "\n",
    "![4queensInstance.png](img/c4_stack_queue/4queensInstance.png)\n",
    "\n",
    "\n",
    "### 费马-拉格朗日分解\n",
    "\n",
    "Fermat-Lagrange 定理指出，任何一个自然数 n 都可以表示为 4 个整数的平方和，如 $30 = 1^2 + 2^2 + 3^2 + 4^2$。\n",
    "\n",
    "采用试探回溯策略解, 分解得到的每个自然数 q 都有 $q <= \\sqrt n = N$，类似 N 皇后问题，其中行数为 4 行，列数为 N 行（即每个自然数的取值）。\n",
    "\n",
    "下面的代码中，对于不超过 n 的每一个自然数，给出了其分解的总数（同一组数的不同排序视作等同），同时给出了 n 的所有分解。\n",
    "\n",
    "```cpp\n",
    "//Fermat-Lagrange 定理：任何一个自然数都可以表示为 4 个整数的平方和，\n",
    "//如 30 = 1^2 + 2^2 + 3^2 + 4^2\n",
    "//试\n",
    "//\n",
    "int nFLSolu = 0; // 保存解的个数\n",
    "int nFLCheck = 0; //保存求解过程中的尝试次数\n",
    "\n",
    "void fermat_lagrange( int n, int counts[] ){ //n 分解\n",
    "    Stack<int> solu; //存放（部分）解的栈\n",
    "    int q = 0; //从第一个自然数开始，相当于第一行\n",
    "    int N = (int)sqrt(n); //列数\n",
    "    int stack_sum = 0; //栈中所有元素的平方和\n",
    "\n",
    "    do { //反复试探与回溯\n",
    "        if ( 4 <= solu.size() || N < q ) { //若已出界，则\n",
    "            q = solu.pop(); //回溯一行，并接着试探该行中的下一列\n",
    "            stack_sum -= q*q;\n",
    "            q++; \n",
    "        } \n",
    "        else { //否则，试探下一行\n",
    "            if (q <=N && stack_sum + q*q <=n) {\n",
    "                solu.push(q);\n",
    "                stack_sum += q*q;\n",
    "\n",
    "                if (4 == solu.size()){\n",
    "                    counts[stack_sum] += 1; //统计不超过 n 的每一自然数的分解数\n",
    "\n",
    "                    if (stack_sum == n){ //局部解是全局解时\n",
    "                        nSolu ++;\n",
    "                        solu.report(\"out\");\n",
    "                    }\n",
    "                }\n",
    "                //q = 0; //下一行开头\n",
    "                //q = q; // 下一行值 >= q，从而能排除同一组数的不同排列\n",
    "\n",
    "            }\n",
    "            else { //q 值及以上的都不符合\n",
    "                q = N+1; //使 q 越界\n",
    "            }\n",
    "\n",
    "        }\n",
    "    } while( ( 0 < solu.size() ) || ( q <= N) );\n",
    "}\n",
    "\n",
    "    int counts[101] = { 0 };\n",
    "    cout << \"fermat_lagrange(100):\" << endl;\n",
    "    fermat_lagrange( 100, counts );\n",
    "    for (int i=0; i<=100; i++){\n",
    "        cout << \"fermat_lagrange \" << i << \" counts: \" << counts[i] << endl;\n",
    "    }\n",
    "\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "### 迷宫寻径\n",
    "\n",
    "nXn 个方格组成的迷宫，除了四周的围墙，还有分布期间的若干障碍物，只能水平或垂直移动。寻径的任务是：在任意指定的起始格点与目标格点之间，找出一条通路（如果的确存在）。\n",
    "\n",
    "![labyrinth_instance.png](img/c4_stack_queue/labyrinth_instance.png)\n",
    "\n",
    "```cpp\n",
    "// 迷宫寻径\n",
    "// nXn 个方格组成的迷宫，除了四周的围墙，还有分布期间的若干障碍物，只能水平或垂直移动。寻径的任务是：在任意指定的起始格点与目标格点之间，找出一条通路（如果的确存在）。\n",
    "\n",
    "//迷宫格点 Cell\n",
    "typedef enum { AVAILABLE, ROUTE, BACKTRACED, WALL } Status; //迷宫单元格点状态\n",
    "// 共 4 种状态： 原始可用，在当前路径上的，所有方向均尝试失败后回溯过的，不可使用的（墙）\n",
    "// 属于当前路径的格点，还需记录其前驱和后继格点的方向。\n",
    "\n",
    "typedef enum { UNKNOWN, EAST, SOUTH, WEST, NORTH, NO_WAY } ESWN;  //单元格点的相对邻接方向\n",
    "// 未定，东，南，西，北，无路可通\n",
    "// 既然只有上下左右四个连接方向，故 E S W N 可区别。特别地，因尚未搜索到而仍处理初始 AVAILABLE\n",
    "// 状态的格点，邻格的方向都是 UNKNOWN，经过回溯后处于 BACKTRACED 状态的格点，与邻格间的连接关系\n",
    "// 均关闭，故标记为 NO_WAY\n",
    "\n",
    "inline ESWN nextESWN( ESWN eswn ) { return ESWN(eswn+1); } //依次转至下一邻接方向\n",
    "\n",
    "struct Cell { //迷宫格点\n",
    "    int x, y; Status status; // 坐标; 状态/类型\n",
    "    ESWN incoming, outgoing; //进入，走出方向，即其前驱和后续格点的方位\n",
    "};\n",
    "\n",
    "\n",
    "#define LABY_MAX 13 //最大迷宫尺寸\n",
    "Cell laby[LABY_MAX][LABY_MAX]; //迷宫，是一个二维数组\n",
    "\n",
    "inline Cell* neighbor (Cell* cell) { //查询当前格点的后继格点\n",
    "    switch( cell->outgoing ){\n",
    "        case EAST: return cell + 1;         // ------->\n",
    "        case WEST: return cell - 1;         // <-------\n",
    "        case SOUTH: return cell + LABY_MAX; //       |\n",
    "                                            //       V\n",
    "        case NORTH: return cell - LABY_MAX; //   ^\n",
    "                                            //   |\n",
    "        default: exit(-1);\n",
    "    }\n",
    "}\n",
    "\n",
    "inline Cell* advance ( Cell* cell ) { //从当前格点转入相邻格点，并设置前驱格点的方向\n",
    "    Cell* next;\n",
    "    switch( cell->outgoing ) {\n",
    "        case EAST:\n",
    "            next = cell + 1;\n",
    "            next->incoming = WEST; break;\n",
    "        case WEST:\n",
    "            next =  cell - 1;\n",
    "            next->incoming = EAST; break;\n",
    "        case SOUTH: \n",
    "            next = cell + LABY_MAX;\n",
    "            next->incoming = NORTH; break;\n",
    "        case NORTH:\n",
    "            next = cell - LABY_MAX;\n",
    "            next->incoming = SOUTH; break;\n",
    "        default: exit(-1);\n",
    "    }\n",
    "    return next;\n",
    "}\n",
    "\n",
    "//实现：借助栈按次序记录组成当前路径的所有格点，\n",
    "//并动态地随着试探、回溯做入栈、出栈操作。\n",
    "//路径的起始格点、当前的末端格点分别对应于路径中的\n",
    "//栈底和栈项，当后者抵达目标格点时探索成功。\n",
    "// 迷宫寻径算法：在格点 s 至 t 之间规划一条通路(如果的确存在）\n",
    "bool labyrinth( Cell Laby[LABY_MAX][LABY_MAX], Cell* s, Cell* t, Stack<Cell*> &path) {\n",
    "    if ( (AVAILABLE != s->status ) || (AVAILABLE != t->status) )\n",
    "        return false; //退化情况\n",
    "\n",
    "    //Stack<Cell*> path; //用栈记录通路\n",
    "\n",
    "    s->incoming = UNKNOWN; //起点\n",
    "    s->status = ROUTE;\n",
    "    path.push(s);\n",
    "\n",
    "    do { //从起点出发不断试探、回溯，直到抵达终点、或穷尽所有可能\n",
    "        Cell* c = path.top(); //检查当前位置（栈顶）\n",
    "        if (c == t) //若已抵达终点，则找到了一条通路，否则沿尚未试探的方向继续试探\n",
    "            return true;\n",
    "\n",
    "        while ( (c->outgoing = nextESWN(c->outgoing)) < NO_WAY ) //逐一检查所有方向\n",
    "            if (AVAILABLE == neighbor(c)->status) //直到找到一个未尝试过的方向\n",
    "                break;\n",
    "\n",
    "        if ( NO_WAY <= c->outgoing ) { //若所有方向都已尝试过\n",
    "            c->status = BACKTRACED; //则标记并且回溯\n",
    "            c = path.pop();\n",
    "        }\n",
    "        else { //还有若尝试的，则向前试探一步\n",
    "            path.push( c=advance(c) );\n",
    "            c->outgoing = UNKNOWN;\n",
    "            c->status = ROUTE;\n",
    "        }\n",
    "    } while (!path.empty());\n",
    "\n",
    "    return false;\n",
    "}\n",
    "\n",
    "    cout << \"test labyrinth:\" << endl; //见P104 的 13X13 实例\n",
    "    for (int i=0; i<LABY_MAX; i++) {\n",
    "        for ( int j=0; j<LABY_MAX; j++) {\n",
    "            laby[i][j].x = i;\n",
    "            laby[i][j].y = j;\n",
    "            laby[i][j].status = AVAILABLE;\n",
    "            laby[i][j].incoming = UNKNOWN;\n",
    "            laby[i][j].outgoing = UNKNOWN;\n",
    "        }\n",
    "    }\n",
    "\n",
    "    for (int i=0; i<LABY_MAX; i++) {\n",
    "        laby[0][i].status = WALL; //第一行\n",
    "        laby[LABY_MAX-1][i].status = WALL; //最后一行\n",
    "\n",
    "        laby[i][0].status = WALL; //第一列\n",
    "        laby[i][LABY_MAX-1].status = WALL; //最后一列\n",
    "    }\n",
    "\n",
    "    laby[1][2].status = WALL;\n",
    "    laby[1][3].status = WALL;\n",
    "    laby[1][6].status = WALL;\n",
    "    laby[2][1].status = WALL;\n",
    "    laby[2][3].status = WALL;\n",
    "    laby[2][4].status = WALL;\n",
    "    laby[2][7].status = WALL;\n",
    "    laby[2][9].status = WALL;\n",
    "    laby[3][5].status = WALL;\n",
    "    laby[3][6].status = WALL;\n",
    "    laby[3][8].status = WALL;\n",
    "    laby[4][5].status = WALL;\n",
    "    laby[5][1].status = WALL;\n",
    "    laby[5][5].status = WALL;\n",
    "    laby[6][5].status = WALL;\n",
    "    laby[7][2].status = WALL;\n",
    "    laby[7][3].status = WALL;\n",
    "    laby[7][6].status = WALL;\n",
    "    laby[7][9].status = WALL;\n",
    "    laby[8][1].status = WALL;\n",
    "    laby[8][6].status = WALL;\n",
    "    laby[9][3].status = WALL;\n",
    "    laby[9][6].status = WALL;\n",
    "    laby[9][7].status = WALL;\n",
    "    laby[9][9].status = WALL;\n",
    "    laby[10][10].status = WALL;\n",
    "    laby[11][8].status = WALL;\n",
    "    laby[11][10].status = WALL;\n",
    "    laby[11][11].status = WALL;\n",
    "\n",
    "    Cell* ss = &laby[4][9];\n",
    "    Cell* tt = &laby[4][1];\n",
    "    Stack<Cell*> path = Stack<Cell*>();\n",
    "\n",
    "    cout << \"has path =\" <<  labyrinth( laby, ss, tt, path) << endl;\n",
    "    while (!path.empty()) {\n",
    "        Cell* c = path.pop();\n",
    "        cout << \"(\" << c->x << \",\" << c->y << \") <-- \";\n",
    "    }\n",
    "    cout << endl;\n",
    "\n",
    "\n",
    "//has path =1\n",
    "//(4,1) <-- (4,2) <-- (4,3) <-- (4,4) <-- (5,4) <-- (5,3) <-- (5,2) <-- (6,2) <-- (6,3) <-- (6,4) <-- (7,4) <-- (7,5) <-- (8,5) <-- (8,4) <-- (9,4) <-- (9,5) <-- (10,5) <-- (10,4) <-- (10,3) <-- (10,2) <-- (10,1) <-- (11,1) <-- (11,2) <-- (11,3) <-- (11,4) <-- (11,5) <-- (11,6) <-- (11,7) <-- (10,7) <-- (10,8) <-- (9,8) <-- (8,8) <-- (8,9) <-- (8,10) <-- (9,10) <-- (9,11) <-- (8,11) <-- (7,11) <-- (6,11) <-- (5,11) <-- (4,11) <-- (4,10) <-- (4,9) <-- \n",
    "```\n",
    "\n",
    "## 队列\n",
    "\n",
    "![queue.png](img/c4_stack_queue/queue.png)\n",
    "\n",
    "队列可用于循环分配器模型中，即轮值（round robin) 算法中：\n",
    "\n",
    "```\n",
    "RoundRobin { //循环分配器\n",
    "    Queue Q(clients); //参不资源分配癿所有客户组成队列Q\n",
    "    while (!ServiceClosed()) { //在服务兲闭乀前,反复地\n",
    "        e = Q.dequeue(); //队首癿客户出队,幵\n",
    "        serve(e); //接叐服务,然后\n",
    "        Q.enqueue(e); //重新入队\n",
    "    }\n",
    "}\n",
    "```\n",
    "\n",
    "### 模拟银行业务处理过程\n",
    "\n",
    "```cpp\n",
    "//列队使用\n",
    "//银行服务模拟\n",
    "//\n",
    "struct Customer{ //顾客类：\n",
    "    int window; //所属窗口（队列）\n",
    "    unsigned int time; //需要的服务时长\n",
    "    int id;\n",
    "};\n",
    "\n",
    "int bestWindow( Queue<Customer> windows[], int nWin) { //为新到顾客确定最佳队列\n",
    "    int minSize = windows[0].size(), optiWin = 0; //最优队列（窗口）\n",
    "    for ( int i=1; i< nWin; i++)\n",
    "        if (minSize > windows[i].size() ) { //挑选出队列最短者\n",
    "            minSize = windows[i].size();\n",
    "            optiWin = i;\n",
    "        } \n",
    "\n",
    "    return optiWin;\n",
    "}\n",
    "\n",
    "//模拟在银行中接受服务的过程\n",
    "void simulate( int nWin, int servTime) { //按指定窗口数，服务总时间模拟银行业务\n",
    "    Queue<Customer>* windows = new Queue<Customer>[nWin]; //为每一窗口创建一个队列\n",
    "\n",
    "    for (int now=0; now<servTime; now++) { //在下班前，每隔一个单位时间\n",
    "        if (rand() % (1+nWin)) { //新顾客以 nWin/(nWin+1) 的概率到达\n",
    "            Customer c;\n",
    "            c.id = now;\n",
    "            c.time = 1 + rand() % 98; //新顾客到达，服务时长随机确定\n",
    "            c.window = bestWindow(windows, nWin); //找出最佳（最短）的服务窗口\n",
    "            windows[c.window].enqueue(c); //新顾客入对应的队列\n",
    "            cout << \"Customer \" << c.id << \" enters Queue \" << c.window << endl;\n",
    "        }\n",
    "\n",
    "        for (int i=0; i< nWin; i++) //分别检查\n",
    "            if (!windows[i].empty()) //各非空队列\n",
    "                if (--windows[i].front().time <= 0) { // 队首顾客的服务时长减少一个单位\n",
    "                    Customer c = windows[i].dequeue(); //服务完毕的顾客出列，由后继顾客接替\n",
    "                    cout << \"Customer \" << c.id << \" leaves Queue \" << c.window << endl;\n",
    "                }\n",
    "    } //for\n",
    "\n",
    "    for (int i=0; i<nWin; i++){\n",
    "        cout << \"Queue \" << i+1 << \" Size:\" << windows[i].size() << endl;\n",
    "    }\n",
    "    \n",
    "    delete [] windows;\n",
    "}\n",
    "\n",
    "simulate(10, 60*8);\n",
    "```"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
